package sword.offer;

/**
 * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class ThirtyNine {
    /**
     * 最优解的方法 摩尔投票
     * 因为这个数字出现的次数会超过数组长度的一半。
     * 所以通过对每个数进行投票，抵消。那么最后这个数肯定胜出！
     * */
    class Solution {
        public int majorityElement(int[] nums) {
            int candidate = nums[0];
            int vote = 1;
            for (int i = 1; i < nums.length; i++) {
                if(vote <= 0){
                    candidate = nums[i];
                }
                if(nums[i] == candidate){
                    vote++;
                }else {
                    vote--;
                }
            }
            return candidate;
        }
    }
}
